Problem statement: zenit13kki

Maroško sa v školskom kole snažil pochopiť zákonitosti medzinárodných ekonomických vzťahov. Keďže ste mu príliš nepomohli, rozhodol sa, že si úlohu trošku zjednoduší. Ak mu nepomôžete ani s týmto, tak sa mu budú ostatní prezidenti posmievať.

Model je nasledovný. Majme dve strany A a B. A dlží B sumu S . V obehu je N typov platidiel, každý má nejakú nominálnu hodnotu. A disponuje niekoľkými kusmi každého z týchto platidiel. B nedisponuje žiadnymi platidlami a nedokáže vydávať. Vie A splatiť svoj dlh presne? Zistite preto minimálny počet kusov platidiel, ktoré musí A zaplatiť B.

Na prvom riadku vstupu sú dve čísla N (1 ≤ N ≤ 50) a S (1 ≤ S ≤ 10,000). Na zvyšných N riadkoch sú popisy platidiel. Na i-tom z týchto riadkov sú dve čísla h_i a p_i. Číslo h_i označuje hodnotu i-teho platidla a p_i označuje počet kusov tohto typu platidla, ktoré má A k dispozícii. Pre každé i platí 1 ≤ h_i ≤ 10,000 a 1 ≤ p_i ≤ 50.

Ak A pomocou svojich platidiel nedokáže presne splatiť sumu S, vypíšte NEDA SA. V opačnom prípade vypíšte minimálny počet kusov platidiel, ktoré na splatenie dlhu treba použiť.

3 19
15 3
6 3
1 17 

4 

2 24
7 3
2 4 

NEDA SA 

6 5613
541 44
90 41
43 50
7651 45
13 48
83 2

21